import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Date;

public class Horsechessboard {
    public static int X;
    public static int Y;
    public static int[][] chess;
    public static boolean[] visited;

    public static boolean finshed;

    public static void main(String[] args) {
        X=6;
        Y=6;
        chess=new int[X][Y];
        visited=new boolean[X*Y];
        int col=1;
        int row=1;
        long t1=System.currentTimeMillis();
        chessboard(chess,1,col-1,row-1);
        long t2= System.currentTimeMillis();
        System.out.println((t2-t1)+"ms");

        for (int[] c:chess) {
            for (int ch:c) {
                System.out.print(ch+"\t\t");
            }
            System.out.println();
        }




    }

    /**
     *
     * @param chess 表示棋盘
     * @param step 用来记录第几步
     * @param col 表示棋盘的列
     * @param row 表示棋盘的行
     */
    public static void chessboard(int[][] chess,int step,int col,int row){
         chess[row][col]=step;
         visited[row * X + col] =true;//用来记录是否访问过
         ArrayList<Point> point=next(new Point(col,row));
         sort(point);//进行排序，将最少选择的那一种最优的走法挑选出来
         while (!point.isEmpty()){
             Point point1=point.remove(0);
             if (!visited[point1.y * X + point1.x]){
                 chessboard(chess,step+1,point1.x,point1.y);
             }
         }
         if (!finshed&&step<X*Y){//如果没有走回起点或没达到步数则回溯
             chess[row][col]=0;//将棋盘置零
             visited[row * X + col]=false;//表示没走完
         }else {
             finshed=true;
         }

    }



    public static ArrayList<Point> next(Point point){
        ArrayList<Point> points=new ArrayList<>();
        Point p1=new Point();
        if ((p1.x=point.x-2)>=0&&(p1.y=point.y-1)>=0){
            points.add(new Point(p1));
        }
        if ((p1.x=point.x-1)>=0&&(p1.y=point.y-2)>=0){
            points.add(new Point(p1));
        }
        if ((p1.x=point.x+2)<X&&(p1.y=point.y-1)>=0){
            points.add(new Point(p1));
        }
        if ((p1.x=point.x+2)<X&&(p1.y=point.y+1)<Y){
            points.add(new Point(p1));
        }
        if ((p1.x=point.x+1)<X&&(p1.y=point.y-2)>=0){
            points.add(new Point(p1));
        }
        if ((p1.x=point.x-1)>=0&&(p1.y=point.y+2)<Y){
            points.add(new Point(p1));
        }
        if ((p1.x=point.x-2)>=0&&(p1.y=point.y+1)<Y){
            points.add(new Point(p1));
        }
        if ((p1.x=point.x+1)<X&&(p1.y=point.y+2)<Y){
            points.add(new Point(p1));
        }
        return points;
    }
    public static ArrayList<Point> sort(ArrayList<Point> points){
         points.sort(new Comparator<Point>() {
             @Override
             public int compare(Point o1, Point o2) {
                 int count1= next(o1).size();
                 int count2=next(o2).size();
                 return count1-count2;
             }
         });
         return points;
    }
}
